Low-density parity check (LDPC) codes are block codes that can provide highly efficient error correction coding (approaching the Shannon limit for large block sizes). LDPC codes introduce redundancy into the transmitted code word in such a way that the parity check matrix is sparse (i.e., has few 1's in each row and column). This enables efficient decoding algorithms.
Encoding of an LDPC code can be performed by multiplying a message word by a generator matrix for the code. Although the parity matrix is sparse, however, the generator matrix is not necessarily sparse. Accordingly, the matrix multiplication can use a large amount of processing. Even when a generator matrix is sparse, straightforward matrix multiplication can be inefficient.
One approach to avoid the high computation cost of direct matrix multiplication is the use of a decoder to perform encoding. In this approach, the information portion of the code word is initialized with transmission data, and the parity bits are initialized to indicate erasure. Decoding is then performed to determine the value of the parity bits. Unfortunately, this approach does not work for all codes.
Efficient code structures have been found for certain designs based on circulant matrices. For example, one approach uses recursive convolutional type encoders based on feedback shift registers. The shift registers are modified from that of a conventional convolutional encoder by providing tap multiplication based on the circulant pattern. The circulant pattern is stored in a shift register and rotated. Unfortunately, this encoder structure still uses a relatively large amount of hardware and is not easily amenable to parallel operation.